#include<stdio.h>
#include<algorithm>
//升序
void insertsort(int *a,int len)
{
    for(int i=1;i<len;i++)
    {
        int tmp=a[i];
        int end=i-1;
        while(end>=0)
        {
            if(tmp<a[end])
            {
                a[end+1]=a[end];
                --end;
            }
            else break;
        }
        
        a[end+1]=tmp;
    }
}

void shellsort(int *a,int len)
{
    int gap=len;
    while(gap>=1)
    {
        gap/=2;
        for(int i=0;i<len-gap;i++)
        {
            int end=i;
            int tmp=a[gap+i];
            while(end>=0)
            {
                if(tmp<a[end])
                {
                    a[end+gap]=a[end];
                    end-=gap;
                }
                else break;
            }
            a[end+gap]=tmp;
        }

    }
}

int main()
{
    int a[]={4,1,2,3,9,2,5,1,2,3};
    int len=(sizeof(a)/sizeof(a[0]));
    // insertsort(a,len);
    shellsort(a,len);
    return 0;
}